/**
 * 二叉树存储数据可以与数组存储数据进行互换；
 * （1）满足完全二叉树
 * （2）顺序存储二叉树：将二叉树转换成的数组，能以”前，中，后序遍历“输出，不是直接输出数组
 *
 * 手动实现，顺序化存储二叉树
 */
public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        //测试
        //创建一个顺序存储二叉树的类
        int[] ints = {1, 2, 3, 4, 5, 6, 7}; //顺序存储二叉树的数组，是按照一定规律生成的
        ArrayBinaryTree tree = new ArrayBinaryTree(ints);
        tree.preOrderArray();   //前序输出数组：1,2,4,5,3,6,7
        System.out.println("--------------------");
        tree.infixOrderArray();  //中序输出数组：4,2,5,1,6,3,7
        System.out.println("--------------------");
        tree.postOrderArray();   //后续输出数组：4,5,2,6,7,3,1
    }
}

//创建一个顺序存储二叉树的类
class ArrayBinaryTree {
    int[] arr;

    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }

    //重载前序存储二叉树方法
    public void preOrderArray() {
        //自动调用
        this.preOrderArray(0);
    }

    //重载中序存储二叉树方法
    public void infixOrderArray() {
        //自动调用
        this.infixOrderArray(0);
    }

    //重载后序存储二叉树方法
    public void postOrderArray() {
        //自动调用
        this.postOrderArray(0);
    }

    //创建前序存储二叉树方法
    private void preOrderArray(int index) {// index:数组的下标,必须从0开始，就相当于二叉树的根节点
        if (arr == null || arr.length == 0) {
            //若数组为空，数组长度为0
            System.out.println("数组为空，没有数据可以前序遍历输出！");
            return;
        }
        //1.直接输出当前节点
        System.out.println(arr[index]);
        //2.递归遍历左子节点
        if (2 * index + 1 < arr.length) {
            this.preOrderArray(2 * index + 1);
        }
        //3.递归遍历右子节点
        if (2 * index + 2 < arr.length) {
            this.preOrderArray(2 * index + 2);
        }
    }//创建前序存储二叉树方法

    //创建中序存储二叉树方法
    private void infixOrderArray(int index) {// index:数组的下标,必须从0开始
        if (arr == null || arr.length == 0) {
            //若数组为空，数组长度为0
            System.out.println("数组为空，没有数据可以前序遍历输出！");
            return;
        }
        //1.递归遍历左子节点
        if (2 * index + 1 < arr.length) {
            this.infixOrderArray(2 * index + 1);
        }
        //2.直接输出当前节点
        System.out.println(arr[index]);
        //3.递归遍历右子节点
        if (2 * index + 2 < arr.length) {
            this.infixOrderArray(2 * index + 2);
        }
    }

    //创建后序存储二叉树方法
    private void postOrderArray(int index) {// index:数组的下标,必须从0开始
        if (arr == null || arr.length == 0) {
            //若数组为空，数组长度为0
            System.out.println("数组为空，没有数据可以前序遍历输出！");
            return;
        }
        //1.递归遍历左子节点
        if (2 * index + 1 < arr.length) {
            this.postOrderArray(2 * index + 1);
        }
        //2.递归遍历右子节点
        if (2 * index + 2 < arr.length) {
            this.postOrderArray(2 * index + 2);
        }
        //3.直接输出当前节点
        System.out.println(arr[index]);
    }//创建后序存储二叉树方法
}